{\ttfamily \raggedright {
% Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite
\noindent
\mbox{}\textbf{\textcolor{Blue}{const}}\ \textcolor{ForestGreen}{int}\ INF\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{1000}\textcolor{BrickRed}{*}\textcolor{Purple}{1000}\textcolor{BrickRed}{*}\textcolor{Purple}{1000}\textcolor{BrickRed}{;} \\
\mbox{}\textbf{\textcolor{Blue}{const}}\ \textcolor{ForestGreen}{int}\ W\ \textcolor{BrickRed}{=}\ \textcolor{BrickRed}{...;}\ \textit{\textcolor{Brown}{//\ peso\ maximo}} \\
\mbox{} \\
\mbox{}\textcolor{ForestGreen}{int}\ n\textcolor{BrickRed}{,}\ s\textcolor{BrickRed}{,}\ t\textcolor{BrickRed}{;} \\
\mbox{}vector\ \textcolor{BrickRed}{$<$}\ vector\ \textcolor{BrickRed}{$<$}\ \textcolor{TealBlue}{pair$<$int,int$>$\ $>$\ $>$}\ g\textcolor{BrickRed}{;} \\
\mbox{}\textcolor{TealBlue}{vector$<$int$>$}\ dist\textcolor{BrickRed}{;} \\
\mbox{}\textcolor{TealBlue}{vector$<$char$>$}\ used\textcolor{BrickRed}{;} \\
\mbox{}\textcolor{TealBlue}{vector$<$int$>$}\ curpath\textcolor{BrickRed}{,}\ kth$\_$path\textcolor{BrickRed}{;} \\
\mbox{} \\
\mbox{}\textcolor{ForestGreen}{int}\ \textbf{\textcolor{Black}{kth$\_$path$\_$exists}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ k\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ maxlen\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ v\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ curlen\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{)}\ \textcolor{Red}{\{} \\
\mbox{}\ \ curpath\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{push$\_$back}}\textcolor{BrickRed}{(}v\textcolor{BrickRed}{);} \\
\mbox{}\ \ \textbf{\textcolor{Blue}{if}}\textcolor{BrickRed}{(}v\ \textcolor{BrickRed}{==}\ t\textcolor{BrickRed}{)}\ \textcolor{Red}{\{} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Blue}{if}}\textcolor{BrickRed}{(}curlen\ \textcolor{BrickRed}{==}\ maxlen\textcolor{BrickRed}{)} \\
\mbox{}\ \ \ \ \ \ kth$\_$path\ \textcolor{BrickRed}{=}\ curpath\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ curpath\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{pop$\_$back}}\textcolor{BrickRed}{();} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Blue}{return}}\ \textcolor{Purple}{1}\textcolor{BrickRed}{;} \\
\mbox{}\ \ \textcolor{Red}{\}} \\
\mbox{}\ \ used\textcolor{BrickRed}{[}v\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Blue}{true}}\textcolor{BrickRed}{;} \\
\mbox{}\ \ \textcolor{ForestGreen}{int}\ found\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
\mbox{}\ \ \textbf{\textcolor{Blue}{for}}\textcolor{BrickRed}{(}\textcolor{TealBlue}{size$\_$t}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}g\textcolor{BrickRed}{[}v\textcolor{BrickRed}{].}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{();}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\ \textcolor{Red}{\{} \\
\mbox{}\ \ \ \ \textcolor{ForestGreen}{int}\ to\ \textcolor{BrickRed}{=}\ g\textcolor{BrickRed}{[}v\textcolor{BrickRed}{][}i\textcolor{BrickRed}{].}first\textcolor{BrickRed}{,}\ \ len\ \textcolor{BrickRed}{=}\ g\textcolor{BrickRed}{[}v\textcolor{BrickRed}{][}i\textcolor{BrickRed}{].}second\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Blue}{if}}\textcolor{BrickRed}{(!}used\textcolor{BrickRed}{[}to\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{\&\&}\ curlen\ \textcolor{BrickRed}{+}\ len\ \textcolor{BrickRed}{+}\ dist\textcolor{BrickRed}{[}to\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{$<$=}\ maxlen\textcolor{BrickRed}{)}\ \textcolor{Red}{\{} \\
\mbox{}\ \ \ \ \ \ found\ \textcolor{BrickRed}{+=}\ \textbf{\textcolor{Black}{kth$\_$path$\_$exists}}\textcolor{BrickRed}{(}k\ \textcolor{BrickRed}{-}\ found\textcolor{BrickRed}{,}\ maxlen\textcolor{BrickRed}{,}\ to\textcolor{BrickRed}{,}\ curlen\ \textcolor{BrickRed}{+}\ len\textcolor{BrickRed}{);} \\
\mbox{}\ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\textcolor{BrickRed}{(}found\ \textcolor{BrickRed}{==}\ k\textcolor{BrickRed}{)}\ \ \textbf{\textcolor{Blue}{break}}\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ \textcolor{Red}{\}} \\
\mbox{}\ \ \textcolor{Red}{\}} \\
\mbox{}\ \ used\textcolor{BrickRed}{[}v\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Blue}{false}}\textcolor{BrickRed}{;} \\
\mbox{}\ \ curpath\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{pop$\_$back}}\textcolor{BrickRed}{();} \\
\mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ found\textcolor{BrickRed}{;} \\
\mbox{}\textcolor{Red}{\}} \\
\mbox{} \\
\mbox{} \\
\mbox{}\textcolor{ForestGreen}{int}\ \textbf{\textcolor{Black}{main}}\textcolor{BrickRed}{()}\ \textcolor{Red}{\{} \\
\mbox{} \\
\mbox{}\ \ \textit{\textcolor{Brown}{//...\ inicializar\ (n,\ k,\ g,\ s,\ t)\ ...}} \\
\mbox{} \\
\mbox{}\ \ dist\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{assign}}\textcolor{BrickRed}{(}n\textcolor{BrickRed}{,}\ INF\textcolor{BrickRed}{);} \\
\mbox{}\ \ dist\textcolor{BrickRed}{[}t\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
\mbox{}\ \ used\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{assign}}\textcolor{BrickRed}{(}n\textcolor{BrickRed}{,}\ \textbf{\textcolor{Blue}{false}}\textcolor{BrickRed}{);} \\
\mbox{}\ \ \textbf{\textcolor{Blue}{for}}\textcolor{BrickRed}{(;;)}\ \textcolor{Red}{\{} \\
\mbox{}\ \ \ \ \textcolor{ForestGreen}{int}\ sel\ \textcolor{BrickRed}{=}\ \textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}n\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)} \\
\mbox{}\ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\textcolor{BrickRed}{(!}used\textcolor{BrickRed}{[}i\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{\&\&}\ dist\textcolor{BrickRed}{[}i\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{$<$}\ INF\ \textcolor{BrickRed}{\&\&}\ \textcolor{BrickRed}{(}sel\ \textcolor{BrickRed}{==}\ \textcolor{BrickRed}{-}\textcolor{Purple}{1}\ \textcolor{BrickRed}{$|$$|$}\ dist\textcolor{BrickRed}{[}i\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{$<$}\ dist\textcolor{BrickRed}{[}sel\textcolor{BrickRed}{]))} \\
\mbox{}\ \ \ \ \ \ \ \ sel\ \textcolor{BrickRed}{=}\ i\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Blue}{if}}\textcolor{BrickRed}{(}sel\ \textcolor{BrickRed}{==}\ \textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{)}\ \ \textbf{\textcolor{Blue}{break}}\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ used\textcolor{BrickRed}{[}sel\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Blue}{true}}\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\textcolor{BrickRed}{(}\textcolor{TealBlue}{size$\_$t}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}g\textcolor{BrickRed}{[}sel\textcolor{BrickRed}{].}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{();}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\ \textcolor{Red}{\{} \\
\mbox{}\ \ \ \ \ \ \textcolor{ForestGreen}{int}\ to\ \textcolor{BrickRed}{=}\ g\textcolor{BrickRed}{[}sel\textcolor{BrickRed}{][}i\textcolor{BrickRed}{].}first\textcolor{BrickRed}{,}\ \ len\ \textcolor{BrickRed}{=}\ g\textcolor{BrickRed}{[}sel\textcolor{BrickRed}{][}i\textcolor{BrickRed}{].}second\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ \ \ dist\textcolor{BrickRed}{[}to\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Black}{min}}\ \textcolor{BrickRed}{(}dist\textcolor{BrickRed}{[}to\textcolor{BrickRed}{],}\ dist\textcolor{BrickRed}{[}sel\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{+}\ len\textcolor{BrickRed}{);} \\
\mbox{}\ \ \ \ \textcolor{Red}{\}} \\
\mbox{}\ \ \textcolor{Red}{\}} \\
\mbox{} \\
\mbox{}\ \ \textcolor{ForestGreen}{int}\ minw\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{,}\ \ maxw\ \textcolor{BrickRed}{=}\ W\textcolor{BrickRed}{;} \\
\mbox{}\ \ \textbf{\textcolor{Blue}{while}}\textcolor{BrickRed}{(}minw\ \textcolor{BrickRed}{$<$}\ maxw\textcolor{BrickRed}{)}\ \textcolor{Red}{\{} \\
\mbox{}\ \ \ \ \textcolor{ForestGreen}{int}\ wlimit\ \textcolor{BrickRed}{=}\ \textcolor{BrickRed}{(}minw\ \textcolor{BrickRed}{+}\ maxw\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{$>$$>$}\ \textcolor{Purple}{1}\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ used\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{assign}}\textcolor{BrickRed}{(}n\textcolor{BrickRed}{,}\ \textbf{\textcolor{Blue}{false}}\textcolor{BrickRed}{);} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Blue}{if}}\textcolor{BrickRed}{(}\textbf{\textcolor{Black}{kth$\_$path$\_$exists}}\textcolor{BrickRed}{(}k\textcolor{BrickRed}{,}\ wlimit\textcolor{BrickRed}{,}\ s\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{==}\ k\textcolor{BrickRed}{)} \\
\mbox{}\ \ \ \ \ \ maxw\ \textcolor{BrickRed}{=}\ wlimit\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Blue}{else}} \\
\mbox{}\ \ \ \ \ \ minw\ \textcolor{BrickRed}{=}\ wlimit\ \textcolor{BrickRed}{+}\ \textcolor{Purple}{1}\textcolor{BrickRed}{;} \\
\mbox{}\ \ \textcolor{Red}{\}} \\
\mbox{} \\
\mbox{}\ \ used\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{assign}}\textcolor{BrickRed}{(}n\textcolor{BrickRed}{,}\ \textbf{\textcolor{Blue}{false}}\textcolor{BrickRed}{);} \\
\mbox{}\ \ \textbf{\textcolor{Blue}{if}}\textcolor{BrickRed}{(}\textbf{\textcolor{Black}{kth$\_$path$\_$exists}}\textcolor{BrickRed}{(}k\textcolor{BrickRed}{,}\ minw\textcolor{BrickRed}{,}\ s\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{$<$}\ k\textcolor{BrickRed}{)} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Black}{puts}}\textcolor{BrickRed}{(}\texttt{\textcolor{Red}{"{}NO\ SOLUTION"{}}}\textcolor{BrickRed}{);} \\
\mbox{}\ \ \textbf{\textcolor{Blue}{else}}\ \textcolor{Red}{\{} \\
\mbox{}\ \ \ \ cout\ \textcolor{BrickRed}{$<$$<$}\ minw\ \textcolor{BrickRed}{$<$$<$}\ \texttt{\textcolor{Red}{'\ '}}\ \textcolor{BrickRed}{$<$$<$}\ kth$\_$path\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{()}\ \textcolor{BrickRed}{$<$$<$}\ endl\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\textcolor{BrickRed}{(}\textcolor{TealBlue}{size$\_$t}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}kth$\_$path\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{();}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)} \\
\mbox{}\ \ \ \ \ \ cout\ \textcolor{BrickRed}{$<$$<$}\ kth$\_$path\textcolor{BrickRed}{[}i\textcolor{BrickRed}{]+}\textcolor{Purple}{1}\ \textcolor{BrickRed}{$<$$<$}\ \texttt{\textcolor{Red}{'\ '}}\textcolor{BrickRed}{;} \\
\mbox{}\ \ \textcolor{Red}{\}} \\
\mbox{} \\
\mbox{}\textcolor{Red}{\}} \\
\mbox{} \\
\mbox{}
} \normalfont\normalsize
